ЛАБОРАТОРНАЯ РАБОТА 4 УПРАВЛЕНИЕ ОСНОВНОЙ ПАМЯТЬЮ В ОС 1. Постановка задач 1.1. Обслуживание запросов на выделение и освобождение памяти реализовано в системе путем ведения списков свободных участков памя- ти с использованием одного из следующих способов выделения памяти: 1) в конце первого участка достаточной длины; 2) в конце наиболее подходящего по длине участка; 3) в конце участка максимальной длины; 4) в начале первого участка достаточной длины; 5) в начале наиболее подходящего по длине участка; 6) в начале участка максимальной длины. Если память выделяется с конца свободного участка, то при осво- бождении памяти список свободных участков упорядочивается по убыва- нию адресов участков. Если память выделяется с начала участка, то участки упорядочиваются по возрастанию адресов. Необходимо определить местонахождение занятых и свободных участков памяти, а также содержимое указателей списка свободных участков после реализации каждого запроса на выделение или освобож- дение памяти. Для каждого варианта условия задачи указан общий объем распределяемой памяти (V), способ выделения памяти (S=1...6), типы запросов (G - выделение памяти, F - освобождение памяти), объем зап- рашиваемой или освобождаемой памяти, адрес освобождаемого участка. ВАРИАНТ 1 ВАРИАНТ 2 ВАРИАНТ 3 ВАРИАНТ 4 ВАРИАНТ 5 ┌────────────┬────────────┬────────────┬────────────┬────────────┐ │V=20000 S=1│V=10000 S=2│V=15000 S=3│V=24000 S=4│V=32000 S=5│ ├────────────┼────────────┼────────────┼────────────┼────────────┤ │G 4000 │G 8000 │G 3000 │G 6000 │G 25000 │ │F 1000-17000│F 3000-7000 │F 1500-13500│F 2000-2000 │F 8000-2000 │ │G 14000 │G 1500 │G 10000 │G 15000 │G 6000 │ │G 2000 │G 2000 │G 1000 │G 2500 │G 500 │ │F 5000-10000│F 1000-9000 │F 4000-4000 │F 3000-11000│F 4000-12000│ │F 2000-15000│F 1000-8000 │F 3000-1000 │F 9500-14000│F 2000-10000│ └────────────┴────────────┴────────────┴────────────┴────────────┘ ВАРИАНТ 6 ВАРИАНТ 7 ВАРИАНТ 8 ВАРИАНТ 9 ВАРИАНТ 10 ┌────────────┬────────────┬────────────┬────────────┬────────────┐ │V=40000 S=1│V=15000 S=2│V=22000 S=3│V=36000 S=5│V=28000 S=6│ ├────────────┼────────────┼────────────┼────────────┼────────────┤ │G 8000 │G 9000 │G 5000 │G 9000 │G 20000 │ │F 3000-34000│F 7000-7000 │F 3000-18000│F 4000-4000 │F 6000-4000 │ │G 27000 │G 4000 │G 13000 │G 24000 │G 5000 │ │G 4000 │G 1000 │G 2000 │G 2000 │G 2000 │ │F 8000-10000│F 3000-2000 │F 5000-10000│F 9000-21000│F 5000-11000│ │F 9000-1000 │F 1000-1000 │F 3000-2000 │F 5000-30000│F 1000-10000│ └────────────┴────────────┴────────────┴────────────┴────────────┘ 1.2. Для уменьшения фрагментации памяти в системе реализован аппарат разделения запросов на выделение памяти по подпулам. Общий объем свободной памяти - 36000 байтов. При отсутствии памяти в под- пуле ему передается последний свободный блок памяти длиной Vблк. Внутри подпула выделяется подходящий участок, находящийся в старших адресах памяти, выделенной подпулу. Необходимо определить состояние памяти (адреса блоков, переданных в подпулы; свободные и занятые участки в подпулах) после реализации каждого запроса на выделение и освобождение памяти. Предполагается, что память из подпула 1 запра- шивается блоками длиной V1, а из подпула 2 - длиной V2 байтов. Зап- росы на выделение и освобождение памяти описываются в виде: Gn[-k] - запрос на выделение памяти из подпула n (n=1,2). Величина k указывает количество повторений запроса (по умолчанию k=1); Fn-m[-k] - запрос на освобождение памяти из подпула n. Освобождается k блоков, выделенных по запросам с номерами m,m+1,...,m+k-1 для данного подпула (по умолчанию k=1). ┌─────┬────┬────┬────┬─────────────────────────────────────────────┐ │N вар│Vблк│ V1 │ V2 │ Запросы на выделение и освобождение памяти │ ├─────┼────┼────┼────┼─────────────────────────────────────────────┤ │ 1 │3000│1000│ 600│G1-4,G2-7,G1-3,F2-1-5,G1-5,F1-4-6,G2-8,F1-1-3│ │ 2 │2000│1000│ 500│G2-6,G1-3,G2-2,F2-1-5,G2,G1-5,F1-1-5,G2-4,G1 │ │ 3 │4000│1000│2000│G1,G2,G2-3,G1-5,F1-5,F2-1-2,G1-7,F1-6-4,G2-3 │ │ 4 │3000│1500│1000│G2-3,G1,G1-2,G2-4,F1-3,G2-2,G1-3,F1-1-2,G2-3 │ │ 5 │2400│ 800│ 600│G2-6,G1-4,F2-1-4,G2-4,F2-9-2,F2-5-2,G1-5,F1-3│ │ 6 │4000│ 800│2000│G1-6,G2-3,G1-4,F1-1-5,G2-2,G1-3,G2,F2-5-2,G1 │ │ 7 │1800│ 600│ 900│G1-4,G2-5,G1-5,F1-1-3,G2-3,F2-3-3,F1-4-3,G2-2│ │ 8 │2000│ 500│1000│G1-2,G2-3,G1-2,F1-2,G2-3,F2-1-5,G1-3,G2,G1-4 │ │ 9 │6000│1200│2000│G2-4,G1-2,G2-3,G1-5,F1-1-5,G2-5,F2-4-6,G1-11 │ │ 10 │3600│ 900│1200│G2-5,G1-5,F1-1-4,G2-4,F2-4-3,G1-7,F1-5-4,G2-6│ └─────┴────┴────┴────┴─────────────────────────────────────────────┘ 1.3. Обслуживание запросов на выделение и освобождение памяти реализовано в системе путем квантования размеров блоков (выделяются блоки памяти длиной 2 в степени k байтов). Необходимо определить расположение занятых и свободных участков памяти, а также содержимое списков свободных блоков после реализации каждого запроса на выделе- ние и освобождение памяти. Для каждого варианта задачи указан общий объем распределяемой памяти (V), типы запросов (G - выделение памя- ти, F - освобождение памяти), объем запрашиваемой или освобождаемой памяти, номер освобождаемого участка памяти (исходя из последова- тельности запросов).   ВАРИАНТ 1 ВАРИАНТ 2 ВАРИАНТ 3 ВАРИАНТ 4 ВАРИАНТ 5 ┌───────────┬───────────┬───────────┬───────────┬───────────┐ │ V = 2048 │ V = 8192 │ V = 4096 │ V = 2048 │ V = 8192 │ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │G 64 │G 512 │G 1024 │G 256 │G 1024 │ │G 256 │G 1024 │G 2048 │G 128 │G 2048 │ │G 256 │G 256 │G 256 │G 512 │G 4096 │ │F 64-1 │F 512-1 │F 1024-1 │F 256-1 │F 1024-1 │ │G 128 │G 2048 │G 128 │G 1024 │G 256 │ │F 256-3 │F 1024-2 │F 256-3 │F 512-3 │F 2048-2 │ │F 256-2 │F 2048-4 8│F 128-4 │F 1024-4 │F 256-4 │ │F 128-4 │F 256-3 │F 2048-2 │F 128-2 │F 4096-3 │ └───────────┴───────────┴───────────┴───────────┴───────────┘ ВАРИАНТ 6 ВАРИАНТ 7 ВАРИАНТ 8 ВАРИАНТ 9 ВАРИАНТ 10 ┌───────────┬───────────┬───────────┬───────────┬───────────┐ │ V = 4096 │ V = 8192 │ V = 2048 │ V = 4096 │ V = 8192 │ ├───────────┼───────────┼───────────┼───────────┼───────────┤ │G 2048 │G 2048 │G 128 │G 1024 │G 2048 │ │G 512 │G 512 │G 1024 │G 1024 │G 256 │ │G 1024 │G 256 │G 256 │G 1024 │G 2048 │ │F 512-2 │F 2048-1 │F 1024-2 │F 1024-2 |F 2048-1 │ │G 128 │G 1024 │G 512 │G 128 │G 1024 │ │F 2048-1 │F 512-2 │F 128-1 │F 1024-1 │F 256-2 │ │F 1024-3 │F 1024-4 │F 512-4 │F 1024-3 │F 2048-3 │ │F 128-4 │F 256-3 │F 256-3 │F 128-4 │F 1024-4 │ └───────────┴───────────┴───────────┴───────────┴───────────┘ 1.4. Обслуживание запросов на освобождение и выделение памяти реализовано в системе MS DOS путем ведения списка блоков управления памятью (MCB). Предполагается, что распределяется свободный участок памяти длиной 20000 параграфов по 10h байт, начинающийся с адреса 1000:0000 (здесь и далее все значения шестнадцатиричные). Необходимо определить местонахождение занятых и свободных участков памяти, а также содержимое MCB после реализации каждого запроса на выделение или освобождение памяти. Варианты условий зада- чи содержат описание различных видов запросов в следующих форматах: L имя n - загрузка на выполнение программы с указанным именем, дли- ной n параграфов; R имя - завершение программы; G n - запрос участка памяти длиной n параграфов; M k-n - изменение длины участка, полученного по k-ому запросу (n - новая длина участка в параграфах); F k - освобождение участка, полученного по k-ому запросу.   ВАРИАНТ 1 ВАРИАНТ 2 ВАРИАНТ 3 ВАРИАНТ 4 ВАРИАНТ 5 ┌──────────┬──────────┬──────────┬──────────┬──────────┐ │ L P1 100 │ L P1 200 │ L P1 300 │ L P1 200 │ L P1 100 │ │ G 200 │ L P2 300 │ G 300 │ G 200 │ G 200 │ │ M 1-100 │ G 100 │ G 100 │ M 1-100 │ G 200 │ │ F 1 │ M 1-150 │ M 1-200 │ L P2 200 │ M 2-300 │ │ L P2 150 │ F 1 │ F 1 │ G 300 │ F 2 │ │ G 300 │ R P2 │ L P2 250 │ F 2 │ L P2 400 │ │ F 2 │ G 500 │ R P2 │ R P2 │ R P2 │ │ R P2 │ F 2 │ F 2 │ F 1 │ F 1 │ │ R P1 │ R P1 │ R P1 │ R P1 │ R P1 │ └──────────┴──────────┴──────────┴──────────┴──────────┘ ВАРИАНТ 6 ВАРИАНТ 7 ВАРИАНТ 8 ВАРИАНТ 9 ВАРИАНТ 10 ┌──────────┬──────────┬──────────┬──────────┬──────────┐ │ L P1 300 │ L P1 200 │ L P1 300 │ L P1 100 │ L P1 400 │ │ G 300 │ L P2 200 │ G 300 │ L P2 300 │ G 400 │ │ M 1-150 │ G 100 │ M 1-200 │ G 200 │ M 1-200 │ │ F 1 │ F 1 │ G 400 │ M 1-100 │ L P2 300 │ │ L P2 200 │ R P2 │ F 1 │ F 1 │ R P2 │ │ R P2 │ G 250 │ L P2 200 │ G 300 │ G 400 │ │ G 500 │ M 2-200 │ R P2 │ F 2 │ F 2 │ │ F 2 │ F 2 │ F 2 │ R P2 │ F 1 │ │ R P1 │ R P1 │ R P1 │ R P1 │ R P1 │ └──────────┴──────────┴──────────┴──────────┴──────────┘ 1.5. Необходимо реализовать на языке Си на IBM PC один из ал- горитмов управления памятью путем разработки следующих функций по выделению и освобождению памяти: void *Malloc(unsigned int) - выделения блока памяти, заданной длины; void *Calloc(unsigned int, unsigned int) - выделения блока памяти, достаточного для размещения заданного количества элементов, указанной длины; void Free(void *, unsigned int) - освобождение блока памяти, распо- ложенного по указанному адресу и имеющего заданную длину. Варианты реализуемых алгоритмов управления памятью: 1) организация списка свободных участков памяти с выделением блоков с конца первого подходящего участка; 2) квантование размеров блоков памяти с выделением блоков, дли- ной 2 в степени k; 3) организация списка свободных участков памяти с выделением блоков с конца наиболее подходящего участка; 4) организация списка свободных и занятых участков памяти, упо- рядоченных по возрастанию адресов участков; 5) организация списка свободных участков памяти с выделением блоков с конца участка максимальной длины; 6) организация списка свободных участков памяти с выделением блоков с начала первого подходящего участка; 7) квантование размеров блоков памяти с определением длины вы- деляемых блоков как чисел, принадлежащих ряду Фибоначи; 8) организация списка свободных участков памяти с выделением блоков с начала наиболее подходящего участка; 9) организация списка свободных и занятых участков памяти, упо- рядоченных по убыванию адресов участков; 10) организация списка свободных участков памяти с выделением блоков с начала участка максимальной длины. 2. Методические указания по выполнению лабораторной работы 2.1. Реализация запросов программ на выделение и освобождение памяти может осуществляться ОС путем организации списка свободных участков памяти. Указатель начала списка содержится в специальной переменной ОС. В начало каждого свободного участка заносится его длина и адрес следующего свободного участка или признак конца списка (например, -1). Список может быть упорядочен по возрастанию или убы- ванию адресов участков. При запросе памяти выбирается подходящий участок, часть которо- го (или весь) выделяется по запросу. Выполняется соответствующая корректировка элементов списка. Выбор осуществляется одним из трех методов: первый достаточный по размеру, наиболее близкий по размеру, максимальный по размеру участок из списка. Требуемый объем памяти может выделяться из начала или конца выбранного участка. По запросу на освобождение памяти проверяется, что освобождае- мый участок принадлежит занятой памяти, создается новый элемент, ко- торый вставляется в список в соответствии с принятым правилом упоря- дочения списка. Если освобождаемый участок примыкает к свободному, то участки объединяются. При выполнении работы 1.1 необходимо показать состояние списка свободных участков после каждого запроса на выделение и осво- бождение памяти. Например, пусть S=1 (память выделяется в конце пер- вого участка достаточной длины, и, соответственно, список упорядочен по убыванию адресов участков), V=10000. Запрос │Указатель Состояние списка памяти │ (10000,-1) Начало │ 0 └──────────────────────────────────────────────────┘ │ 0 10000 │ │ (4000,-1) G 6000 │ 0 └───────────────────┴▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀┘ │ 0 4000 10000 │ │ (4000,-1) (2000,0) F 2000-│ 6000 └───────────────────┴▀▀▀▀▀▀▀▀▀┴──────────┴▀▀▀▀▀▀▀▀▀┘ 6000 │ 0 4000 6000 8000 10000 │ (1000,-1) (2000,0) G 3000 │ 6000 └─────┴▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀┴──────────┴▀▀▀▀▀▀▀▀▀┘ │ 0 1000 6000 8000 10000 │ │ (1000,-1) (1000,0) (2000,3000) F 1000-│ 6000 └─────┴▀▀▀▀▀▀▀▀┴─────┴▀▀▀▀▀▀▀▀┴──────────┴▀▀▀▀▀▀▀▀▀┘ 3000 │ 0 1000 3000 4000 6000 8000 10000 │ (1000,-1) (5000,0) F 2000-│ 3000 └─────┴▀▀▀▀▀▀▀▀┴─────────────────────────┴▀▀▀▀▀▀▀▀▀┘ 4000 │ 0 1000 3000 8000 10000 2.2. Подпулом называется логически выделенная часть памяти, предназначенная для обслуживания групп однородных запросов на па- мять. Свободная память передается в подпул и возвращается из него блоками большого размера, что уменьшает фрагментацию памяти по срав- нению с чередованием в памяти свободных и занятых участков различной длины. При выполнении работы 1.2 необходимо показать состояние памя- ти после каждого запроса на выделение и освобождение памяти. Напри- мер, пусть Vблк=3000, V1=1000, V2=1500. Запрос Состояние памяти │ Начало ... ─────────────────────────────────────────────────────┘ 36000 │ 2.3 │ 2.2 2.1 │ G2-3 ... ──────────────────────────────┴────┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┘ 30000 33000 36000 │ 1.2 1.1│ 2.3 │ 2.2 2.1 │ G1-2 ... ──────────────────┴───┴▀▀▀┴▀▀▀┴────┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┘ 27000 30000 33000 36000 │ 2.6 2.5 │ 1.2 1.1│ 2.4 2.3 │ 2.2 2.1 │ G2-3 ... ─────┴▀▀▀▀▀┴▀▀▀▀▀┴───┴▀▀▀┴▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┘ 24000 27000 30000 33000 36000 │ 2.6 2.5 │ 1.2 1.1│ 2.4 2.3 │ │ F2-1-2 ... ─────┴▀▀▀▀▀┴▀▀▀▀▀┴───┴▀▀▀┴▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┴───────────┘ 24000 27000 30000 33000 36000 │ 2.6 2.5 │1.3 1.2 1.1│ 2.4 2.3 │1.6 1.5 1.4│ G1-4 ... ─────┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀┴▀▀▀┴▀▀▀┴▀▀▀▀▀┴▀▀▀▀▀┴▀▀▀┴▀▀▀┴▀▀▀┘ 24000 27000 30000 33000 36000 2.3. При квантовании размеров блоков память предоставляется блоками длиной 2 в степени k. Если размер памяти 2 в степени s, то система ведет s+1 список, причем k-ый список LIST(k) содержит адреса свободных блоков длиной 2 в степени k. Первоначально все списки пусты, кроме LIST(s), который указывает на первое слово свободной памяти. Выделение блока длиной 2 в степени k начинается с просмотра LIST(k). Если этот список не пуст, то предоставляется один из его блоков. Иначе, проверяется LIST(k+1). Если этот список не пуст, то один из его блоков расщепляется: одна половина выделяется по зап- росу, другая помещается в LIST(k). Если LIST(k+1) пуст, то просмат- ривается LIST(k+2) и т.д до LIST(s). Если все списки LIST(j) при k<=j<=s пусты, то запрос не удовлетворяется. Например, пусть объем распределяемой памяти 1024 байта, S=10. Первоначально LIST(10)={0}, что соответствует одному свободному блоку длиной 1024 байта. Получен запрос на 64 байта, что соответствует k=6. Списки LIST(6)-LIST(9) пусты. Исходный блок и получаемые блоки меньшего размера, начинающиеся с адреса 0, последовательно расщепляются: LIST(10)={},LIST(9)={0,512}; LIST(10)={},LIST(9)={512},LIST(8)={0,256}; LIST(10)={},LIST(9)={512},LIST(8)={256}, LIST(7)={0,128}; LIST(10)={},LIST(9)={512},LIST(8)={256},LIST(7)={128},LIST(6)={0,64} Блок, начинающийся с адреса 0, выделяется по запросу, и корректиру- ется LIST(6)={64}. При освобождении блока длиной 2 в степени k ссылка на него за- носится в LIST(k). Если LIST(k) содержит элемент для смежного блока, полученного в результате расщепления, то блоки объединяются, элемен- ты для смежных блоков удаляются из LIST(k), создается соответствую- щий элемент LIST(k+1) и т.д. Далее приводятся состояния списков и распределение свободных и занятых участков памяти при выполнении некоторой последовательности запросов на выделение и освобождение памяти.  ш1.4 Список ║ Начало│ G 64 │ G 256 │ G 256 │ G 64 │ F 64-1 │ F 64-2 ────────╫───────┼────────┼───────┼───────┼───────┼────────┼──────── 10 ║ 0 │ │ │ │ │ │ 9 ║ │ 512 │ 512 │ │ │ │ 8 ║ │ 256 │ │ 768 │ 768 │ 768 │ 0,768 7 ║ │ 128 │ 128 │ 128 │ 128 │ 128 │  Л- 6 ║ │ 64 │ 64 │ 64 │ │ 0 │  Л+ Начало └────────────────────────────────────────────────┘ 0 1024 G 64 └▀▀┴──┴─────┴────────────┴───────────────────────┘ 0 64 128 256 512 1024 G 256 └▀▀┴──┴─────┴▀▀▀▀▀▀▀▀▀▀▀▀┴───────────────────────┘ 0 64 128 256 512 1024 G 256 └▀▀┴──┴─────┴▀▀▀▀▀▀▀▀▀▀▀▀┴▀▀▀▀▀▀▀▀▀▀▀┴───────────┘ 0 64 128 256 512 768 1024 G 64 └▀▀┴▀▀┴─────┴▀▀▀▀▀▀▀▀▀▀▀▀┴▀▀▀▀▀▀▀▀▀▀▀┴───────────┘ 0 64 128 256 512 768 1024 F 64-1 └──┴▀▀┴─────┴▀▀▀▀▀▀▀▀▀▀▀▀┴▀▀▀▀▀▀▀▀▀▀▀┴───────────┘ 0 64 128 256 512 768 1024 F 64-2 └───────────┴▀▀▀▀▀▀▀▀▀▀▀▀┴▀▀▀▀▀▀▀▀▀▀▀┴───────────┘ 0 256 512 768 1024 2.4. Для того чтобы отслеживать распределение памяти, MS DOS ведет список блоков управления памятью - MCB. Каждый MCB занимает целый параграф и непосредственно предшествует определяемому блоку памяти - непрерывной области памяти, начинающейся на 16-байтовой границе. MCB упорядочены по возрастанию адресов памяти, адрес перво- го MCB хранится в специальной переменной MS DOS. Структура MCB: байт 0 - символ 'Z', если блок последний в списке, 'M' - в про- тивном случае; байты 1-2 - равны нулю, если блок свободен. Иначе, байты содержат идентификатор программы (PID) - сегментную часть адреса префикса сегмента программы (PSP). PSP - управляющий блок длиной 100h байт, предшествующий программе; байты 3-4 - длина блока в параграфах без учета длины MCB; байты 5-15 - не используются. Используются следующие правила выделения и освобождения памяти: 1) память выделяется из первого подходящего по размерам свобод- ного участка; 2) при уменьшении размера занятого блока для описания освобо- дившегося участка создается новый MCB; 3) при освобождении блока делается только отметка в MCB; 4) при выделении памяти смежные свободные участки объединяются. Например, пусть распределяется память, начиная с адреса 1000:0000 длиной 10000 параграфов. Тогда 1000 - номер первого расп- ределяемого параграфа. Начальное состояние памяти: ┌─┬────┬──────┐ 1000 │Z│0000│ FFFF │ ├─┴────┴──────┤ │ │ └─────────────┘ Далее приводится пример обработки запросов на загрузку програм- мы, выделение и освобождение памяти, изменение размеров блоков. L P1 200 G 180 M 1-300 ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1000 │M│1001│210 ├┐ 1000 │M│1001│210 │ 1000 │M│1001│210 │ ├─┴────┴──────┤│ ├─┴────┴──────┤ ├─┴────┴──────┤ 1001 │ PSP(10) ││ │ PSP(10) │ │ PSP(10) │ │ ├─────────────┤│ ├─────────────┤ ├─────────────┤ │ │ P1(200) ││ │ P1(200) │ │ P1(200) │ │ └─────────────┘│ └─────────────┘ └─────────────┘ + <────────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1211 │Z│0000│ FDEE │ 1211 │M│1001│180 ├┐ 1211 │M│1001│300 ├┐ ├─┴────┴──────┤ ├─┴────┴──────┤│ ├─┴────┴──────┤│ │ │ 1212 │ (200) ││ 1212 │ (300) ││ └─────────────┘ │ └─────────────┘│ │ └─────────────┘│ + <────────────────┘ + <────────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1392 │Z│0000│ FC6D │ 1512 │Z│0000│ FAED │ ├─┴────┴──────┤ ├─┴────┴──────┤ │ │ │ │ └─────────────┘ └─────────────┘ M 1-180 F 1 G 280 ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1000 │M│1001│210 │ 1000 │M│1001│210 │ 1000 │M│1001│210 │ ├─┴────┴──────┤ ├─┴────┴──────┤ ├─┴────┴──────┤ │ PSP(10) │ │ PSP(10) │ │ PSP(10) │ ├─────────────┤ ├─────────────┤ ├─────────────┤ │ P1(200) │ │ P1(200) │ │ P1(200) │ └─────────────┘ └─────────────┘ └─────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1211 │M│1001│180 ├┐ 1211 │M│0000│180 │ 1211 │M│1001│280 ├┐ ├─┴────┴──────┤│ ├─┴────┴──────┤ ├─┴────┴──────┤│ 1212 │ (180) ││ │ │ 1212 │ (280) ││ │ └─────────────┘│ └─────────────┘ │ └─────────────┘│ + <────────────────┘ + <────────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1392 │M│0000│17F ├┐ 1392 │M│0000│17F │ 1492 │M│0000│7F ├┐ ├─┴────┴──────┤│ ├─┴────┴──────┤ ├─┴────┴──────┤│ 1393 │ ││ │ │ 1493 │ ││ │ └─────────────┘│ └─────────────┘ │ └─────────────┘│ + <────────────────┘ + <────────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1512 │Z│0000│ FAED │ 1512 │Z│0000│ FAED │ 1512 │Z│0000│ FAED │ ├─┴────┴──────┤ ├─┴────┴──────┤ ├─┴────┴──────┤ │ │ │ │ │ │ └─────────────┘ └─────────────┘ └─────────────┘ F 2 R P1 ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1000 │M│1001│210 │ 1000 │M│0000│210 │ ├─┴────┴──────┤ ├─┴────┴──────┤ │ PSP(10) │ │ │ ├─────────────┤ └─────────────┘ │ P1(200) │ └─────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1211 │M│0000│280 │ 1211 │M│0000│280 │ ├─┴────┴──────┤ ├─┴────┴──────┤ │ │ │ │ └─────────────┘ └─────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1492 │M│0000│7F │ 1492 │M│0000│7F │ ├─┴────┴──────┤ ├─┴────┴──────┤ │ │ │ │ └─────────────┘ └─────────────┘ ┌─┬────┬──────┐ ┌─┬────┬──────┐ 1512 │Z│0000│ FAED │ 1512 │Z│0000│ FAED │ ├─┴────┴──────┤ ├─┴────┴──────┤ │ │ │ │ └─────────────┘ └─────────────┘ 2.5. При выполнении работы 1.5 для реализации запросов на выделение и освобождение памяти должен быть зарезервирован внешний массив длиной 32Кбт, используемый разрабатываемыми функциями в ка- честве распределяемой области памяти. Таким образом, возвращаемые функциями Malloc, Calloc адреса будут являться адресами соответству- ющих элементов этого массива. Некоторые указания и рекомендации по выполнению лабораторной работы: 1) списки участков (вар. 1, 3-6, 8-10) должны организовываться внутри зарезервированного массива (кроме указателя начала списка). Величину запросов на выделение памяти рекомендуется округлять в большую сторону до длины управляющей информации, размещаемой внутри участков; 2) реализация вариантов 1, 3, 5, 6, 8, 10 предполагает включе- ние в список только свободных участков (аналогично задаче 4.1.1). Параметры функции Free могут определять произвольные участки внутри занятой памяти, необязательно совпадающие с выделенными участками: 3) при ведении списков свободных и занятых участков (вар. 4, 9) функция Free должна иметь только один параметр (могут освобождаться только те участки, адреса которых были получены по запросам на выде- ление памяти); 4) при реализации квантования размеров блоков (вар. 2, 7), вто- рой параметр функции Free может использоваться для определения номе- ра списка, в который должна включаться ссылка на освобождаемый блок. Для пользователя допускается освобождение только тех блоков, которые непосредственно были получены; 5) реализация варианта 7 предполагает определение размера бло- ков как чисел ряда Фибоначи: f(0)=f(1)=1, f(i)=f(i-1)+f(i-2) (1,1,2,3,5,8,13,...). При отсутствии свободного блока необходимой длины, блок из списка с большим номером k должен расщепляться на блоки из списков с номерами k-1, k-2.